import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: AliceMana
 * Date: 2022-10-12
 * Time: 8:10
 */
public class TestHeap {
    public int[] elem;
    public int usedSize;

    public static final int DEFAULT_SIZE = 10;

    public TestHeap() {
        this.elem = new int[DEFAULT_SIZE];
    }

    // 初始化堆
    public void initElem(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            elem[i] = arr[i];
            usedSize++;
        }
    }

    public void createHeap() {
        for (int parent = (usedSize-1-1)>>1; parent >= 0; parent--) {
            // 统一向下调整
            shiftDown(parent, usedSize);
        }
    }

    /**
     * 向下调整
     * @param parent 每棵子树的根节点
     * @param len 每棵子树调整结束的位置， 不能大于len
     *            时间复杂度     O(log n)
     */
    private void shiftDown(int parent, int len) {
        int child = 2*parent+1;

        // 保证有右孩子
        while (child < len) {
            // 让child指向左右孩子的最大值
            if (child+1<len && elem[child] < elem[child+1]) {
                child++;
            }

            // 开始调整
            if (elem[parent] < elem[child]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                // 更新根节点 以及 孩子
                parent = child;
                child = 2*parent+1;
            } else {
                break;
            }
        }
    }

    // 判断堆内是否为空
    public boolean isEmpty() {
        return usedSize == 0;
    }

    // 判断堆是否满了
    public boolean isFull() {
        return usedSize == elem.length;
    }

    // 获取优先级队列顶部的元素
    public int peek() {
        if (isEmpty()) {
            throw new EmptyException("堆内为空!");
        }
        return elem[0];
    }

    // 将元素添加进堆内
    public void offer(int val) {
        if (isFull()) {
            elem = Arrays.copyOf(this.elem, 2*elem.length);
        }
        this.elem[usedSize] = val;
        usedSize++;

        shiftUp(usedSize-1);
    }

    /**
     * 向上调整
     * @param child 要调整的节点
     */
    private void shiftUp(int child) {
        int parent = (child - 1) >> 1;
        while (child > 0) {
            if (elem[child] > elem[parent]) {
                // 交换父亲节点和孩子节点
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                // 更新父节点和孩子节点
                child = parent;
                parent = (child-1) >> 1;
            } else {
                break;
            }
        }
    }

    public void pop() {
        if (isEmpty()) {
            return;
        }
        int tmp = elem[0];
        elem[0] = elem[usedSize-1];
        elem[usedSize-1] = tmp;
        usedSize--;
        // 开始向下调整
        shiftDown(0, usedSize);
    }

}
